1. Field of the Invention
The present invention relates to an error correction method for effecting Q- or P-sequence error correction on data stored in a CD-ROM.
2. Description of the Prior Art
CD-ROMs store digital data on compact disks (CD) that can be played back by CD players. The CD-ROMs are required to have a bit error rate of 10.sup.-12 or below as with other computer devices. Generally, the bit error rate of CDs themselves is about 10.sup.-9. Therefore, in addition to the error correction capability of CDs, CD-ROMs have another error correction code that is complete in each block composed of 98 frames of the CD. The other error correction code of the CD-ROMs is a product code of P and Q sequences.
FIG. 1 of the accompanying drawings shows the format of one block of data stored in a CD-ROM. In FIG. 1 one block comprises 2352 bytes (bytes are indicated by B) of data including, successively from-the leading end, a synchronizing pattern of 12 bytes, a header of 4 bytes indicating an absolute time and a mode, user data of 2048 bytes, a CRC (cyclic redundancy check) code, a pattern of zeros of 8 bytes, P-sequence parity (P parity) check data of 172 bytes, and Q-sequence parity (Q parity) check data of 104 bytes. The 4-byte CRC code is used to finally check whether the data have errors or not, after the reproduced data have been subjected to P- and Q-sequence error correction. The CRC code is effective with respect to the data of 2064 bytes that include the synchronizing pattern, the header, and the user data.
The data format shown in FIG. 1 is a format for the mode 1. For the mode 2, the pattern of zeros of 8 bytes is dispensed with, and a subheader of 8 bytes is inserted between the header and the user data.
From the data of 2352 bytes shown in FIG. 1, the synchronizing pattern of 12 bytes is removed, and the remaining data of 2340 bytes are divided into two data groups each of 1170 bytes. One of the data groups as it is interleaved is shown in FIG. 2. In FIG. 2, the bytes of data are designated by D0, D1, . . . , D1169 successively from the leading end of the data group. The user data D0 through D1031 are arranged in 24 rows and 43 columns, the P parity data D1032 through D1117 in 2 rows and 43 columns, and the Q parity data D1118 in 2 rows and 26 columns. The P sequence is a sequence in each of the 43 columns, and the Q sequence is a sequence diagonally across the matrix of 26 rows.times.43 columns. More specifically, 2 bytes of P parity are added to the user data of 24 bytes in each of the 43 columns, and 2 bytes of Q parity are added to the diagonal data of 43 bytes (including the 2 bytes of P parity).
It is assumed that one word is represented by m bits, overall data by n words, user data except parity data by k words, and a Reed-Solomon code defined on a Galois field GF(2.sup.m) with the minimum distance d in an error-free condition is a (m, n, k, d) code. In CD-ROMs, one word is represented by one byte, the P sequence by a (8, 26, 24, 3) code having two words of parity, and the Q sequence by a (8, 45, 43, 3) code having two words of parity. The error correction code for CD-ROMs is a product code of the Reed-Solomon code defined on the Galois field GF(2.sup.8). If there are two words of parity, then one word of error can accurately be corrected, and two words of error can also accurately be corrected provided the position of the error is known from a pointer.
One block of data in a CD-ROM, as shown in FIG. 1, corresponds to 98 frames of data each of 24 bytes in a CD. When one block of data is recorded in a CD-ROM, a CIRC (cross interleave Reed Solomon code) composed of a C1-sequence Reed-Solomon code and a C2-sequence Reed-Solomon code that are coupled by interleaving is added to the data. FIG. 3 shows the manner in which such a CIRC as an error correction code for CDs is encoded. As shown in FIG. 3, each of data groups 1 of 24 words (=24 bytes) is scrambled, and then 4 words of C2-sequence parity are added to each data group of 24 words, forming a data group 2. After the data of each data group 2 of 28 words is interleaved, 4 words of C1-sequence parity are added to each data group of 28 words, forming a data group 3. For details of product codes for CDs themselves, reference should be made to Japanese Laid-Open Patent Publications Nos. 57-4629 and 57-6417.
The C2 sequence is a Reed-Solomon code of (m=8, n=28, k=24, d=5), and the C1 sequence is a Reed-Solomon code of (m=8, n=32, k=28, n=5). Even if no pointer is used, a 2-word random error with respect to each data of 32 words can be corrected with the C1-sequence parity code, and a 2-word random error with respect to each data of 28 words can be corrected with the C2-sequence parity code. If any data remain that cannot finally be corrected with the C1- and C2-sequence error correction codes, then a pointer indicating that the data are presumed to be incorrect is set with respect to the data.
An overall sequence of error correction for the data in a CD-ROM will be described below with reference to FIG. 4. A product code of C1 and C2 sequences of a CD itself is added to each block of data shown in FIG. 1, and a signal produced by modulating the resultant data according to EFM or the like is recorded in the CD-ROM. In a reproducing system for the CD-ROM, data corresponding to CD frames are successively read from the CD-ROM, and demodulated in a step 100. After the read data are shuffled, the data of each frame of 32 words are subjected to the C1-sequence error correction for CDs, producing data of 28 words in a step 101.
If the 32 words contain an error of 3 words or more, then it is impossible to correct the error completely. If the error correction is not complete, then a C1 pointer is set which indicates that the data of each frame of 32 words is presumed to be incorrect, i.e., the C1 pointer is set to a high level of "1" with respect to the data of each frame of 28 words in a step 102. Actually, it has been proposed to set the C1 pointer for all the data for safety reason in the event that a 2-word error is corrected according to the C1-sequence error correction. However, since the data with respect to which the C1 pointer has been set contain correct data, the C1 pointer may be considered as indicating data which may possibly contain an error.
Thereafter, one word of data is extracted from every five frames of the 108 frames of data which have been decoded according to the C1 sequence, and the C2-sequence error correction is effected on the extracted 28 words of data in a step 103. According to the C2 sequence, 4 words of the 28 words of data are parity words, and the C1 pointer has been added indicating whether the data of each of the 28 words is in error or not. Therefore, a 4-word error can be corrected from a theoretical standpoint. However, even when the C2-sequence error correction is carried out, the error correction may not completely be effected on the 24 words except the parity words. In the event that the error correction is not completely effected on the 24 words, a C2 pointer is set which indicates that each of the 24 words of data is presumed to be incorrect, i.e., the C2 pointer is set to a high level of "1" with respect to each of the 24 words of data in a step 104. The C1 pointer that has been supplied from the previous stage may be reproduced as the C2 pointer.
The decoder which has effected the error correction on the CD data supplies, in a step 105, the CD-ROM decoder with 2352 (=24.times.94) words of data, which have been subjected to the error correction, of one block of the CD-ROM corresponding to 98 frames of the CD, and the C2 pointers of 2352 bits indicating of whether the respective words are in error or not. The CD-ROM decoder effects Q-sequence error correction on 45 words (2 words thereof are parity words) of data of the Q sequence shown in FIG. 2 in a step 106, and sets a pointer to a high level of "1" with respect to those words which are presumed not to be error-corrected completely in a step 107.
Thereafter, the CD-ROM decoder effects P-sequence error correction on 26 words (2 words thereof are parity words) of data of the P sequence shown in FIG. 2 in a step 108, and sets a pointer to a high level of "1"0 with respect to those words which are presumed not to be error-corrected completely in a step 109. In a step 110, errors are detected from the synchronizing pattern, the header, and the user data using the CRC code. Thereafter, the CD-ROM decoder supplies a host computer with the error-corrected data, the pointers added to the data, and the result of error detection using the CRC code in a step 111. Then, next data are read in a step 112.
Since the product code of P and Q sequences is added to the usual CD error correction code, the data stored in the CD-ROMs are highly reliable as the bit error rate thereof is 10.sup.-12 or less.
Recently, however, there is a demand for higher reliability of CD-ROM data. To achieve higher reliability means to reduce the probability of erroneous correction and the probability of correction failures. In addition, there is also a demand for the real-time reproduction of data from CD-ROMs while effecting error correction on the data at high speed.
Heretofore, the P- and Q-sequence error correction has been effected on CD-ROM data by carrying out complex calculations based on software. The conventional process is not suitable for relatively small systems to increase the speed of the error correction procedure.